
#include <iostream>
#include <vector>
#include <string>
#include <string.h>
#include <climits>
using namespace std;
// 路径问题
class Solution1
{
public:
    int uniquePaths(int m, int n)
    {
        if (m == 0 && n == 0)
            return 1;
        // vector可以自动初始化数组为0！
        vector<vector<int>> dp(m + 1, vector<int>(n + 1)); // 二维数组多开一行和一列，作为虚拟节点
        dp[0][1] = 1;                                      // 也可以[1,0]位置为1start位置就有1种方法
        for (int i = 1; i <= m; ++i)                       // 我们最外面的一行一列虚拟节点因为vector创建数组自动初始化0，所以就都初始化完毕了
        {
            for (int j = 1; j <= n; ++j) // 所以行列都从1开始
            {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
        // for(int i = 0;i<=m;++i)
        // {
        //     for(int j = 0;j<=n;++j)
        //     {
        //         dp[i][j] = dp[i-1][j]+dp[i][j-1];
        //         // if(i==0 && j==1)
        //         //     dp[i][j] = 1;// start如果是终点，那么就为1，我们可以让[i,j]为1，也可以让[j][i]为1,这样start位置就有1种方法了
        //         // else if(i>0 && j>0)
        //         // {
        //         //     // 状态转移方程，该位置可以由上面位置和左边位置得到，所以方法就是上面位置方法数 + 左边位置方法数
        //         //     dp[i][j] = dp[i-1][j]+dp[i][j-1];
        //         // }
        //         // else
        //         //     dp[i][j] = 0;// 初始化用的，因为我们上面把start已经初始化为1了，可以根据start得到其他位置的值，所以全部为0
        //     }
        // }
        // return dp[m][n];
    }
};

//  路径问题II
class Solution2
{
public:
    int uniquePathsWithObstacles(vector<vector<int>> &obstacleGrid)
